Cwiczenie 6

/* Cwiczenie 6 */

#include <stdio.h>
#include <stdlib.h>  /* Funkcja system()         */
#include <assert.h>  /* Makroinstrukcja assert() */

/* Definijemy typ uint jako typ unsigned int. */
typedef unsigned int uint;

/* Definiujemy typ bool i stale dla dzialan logicznych. */
/* Dla oszczednosci pamieci wybierzemy typ char.        */
typedef char bool;
#define true 1
#define false 0


#define MAX_PIERWSZA 10000000    /* Rozmiar tablicy prawdy */

bool czyPierwsza(uint liczba) {
    static bool pierwsze[MAX_PIERWSZA];  /* Talica prawdy     */
    static bool init = false;            /* Zainicjalizowana? */

    /* Uzyte zmienne statyczne zostana utworzone tylko raz, */
    /* przy pierwszym wejsciu do ciala funkcji. Usuwane sa  */
    /* dopiero przy zakonczeniu pracy programu.             */

    /* Najpierw sprawdzimy czy liczba miesci sie w zakresie */
    /* Makroinstrukcja assert wylaczy program, gdy warunek  */
    /* nie zostanie spelniony.                              */

    assert(liczba < MAX_PIERWSZA);

    /* Jezeli jestesmy pierwszy raz w ciele funkcji, musimy */
    /* zainicjalizowac tablice prawdy.                      */

    if (!init) {
        uint i, j;   /* Liczniki petli */

        /* Zastosujemy prosty algorytm - Sito Eratostenesa.     */
        /* Jest on bardzo wydajny jesli chodzi o zlozonosc      */
        /* obliczeniowa, ale potrzebuje duzej ilosci pamieci.   */
        /* Domyslnie przyjmiemy, ze liczba jest pierwsza. Potem */
        /* bedziemy sukcesywnie usuwac wielokrotnosci kolejnych */
        /* liczb, przez co w tablicy prawdy zostana nam tylko   */
        /* liczby pierwsze.                                     */

        pierwsze[0] = false;
        pierwsze[1] = false;

        for (i = 2; i < MAX_PIERWSZA; i++)
            pierwsze[i] = true;

        for (i = 2; i < MAX_PIERWSZA; i++)
            for (j = 2*i; j < MAX_PIERWSZA; j += i)
                pierwsze[j] = false;

        /* Ustawiamy flage inicjalizacji na true. */
        init = true;
    }

    /* Zwracamy wartosc tablicy prawdy. */
    return pierwsze[liczba];
}


/* Test! */
/* Definiujemy prosta funkcje do testow. */
void test(uint x) {
    if (czyPierwsza(x))
        printf("Liczba %u jest pierwsza!\n", x);
    else
        printf("Liczba %u nie jest pierwsza!\n", x);
}


int main(void) {
    puts("Rozpoczecie pracy programu!");
    test(12435);
    test(1);
    test(12934);
    test(2);

    puts("\nTeraz nastapi proba sprawdzenia zbyt duzej liczby!\n");
    system("pause");
    test(MAX_PIERWSZA);


    return 0;
}